#ifndef __LINKEDLISTZ_H
#define __LINKEDLISTZ_H

#include <iterator>

namespace datastructureZ
{
/*	TITLE:双向循环链表实现
 *	AUTHOR:兰兰
 *	DEVELOP VERSION:3
 *	RELEASE VERSION:1
 *	TIME 05/16/2021-17:31
 *
 *	术语约定：采用“节点”而非“结点”，着重体现数据的逻辑结构
 *	实现细节：
 *		节点具有前后向指针
 *		具有空的头节点
 *		空的头结点为哨兵节点(nil)，同样作为尾部节点
 *		最后一个元素的后向指针指向nil
 *		设计实现了双向迭代器，用户开发者可以通过迭代器或者成员函数访问元素
 *
 *	           O 
 *	          / \
 *	entry -> X   O
 *	(nil)     \ /
 *	           O
 */
template<typename ElementType> class LinkedList
{
	public:class iterator;
	//链表节点定义
	public:class Node
	{
		friend class iterator;
		friend class LinkedList;	//友元声明
		
		private:ElementType data;	//存储的数据
		
		private:Node* pre;			//前向指针
		private:Node* next;			//后向指针
		
		//构造函数，前后向指针初始化为this以避免对空指针解引用 
		public:Node(const ElementType& e):data(e), pre(this), next(this){}
		public:Node(void):pre(this), next(this){}
		
		//拷贝构造函数已显式定义
		public:Node(const Node& another):data(another.data), pre(another.pre), next(another.next){}
	};
	
	//部分数据成员，还有一部分在迭代器类定义之后，为起始和终止迭代器
	//-----------------[data]-----------------
	private:Node *const entry;
	//-----------------[data]-----------------
	
	//获取只读的入口节点
	public:const Node* getEntry(void)
	{
		return entry;
	}
	
	//迭代器类定义，类命名规范遵从C++ STL习惯(采用全小写)
	public:class iterator:public std::iterator
	<
		std::bidirectional_iterator_tag, 
		ElementType,	Node*, 
		ElementType*,	ElementType&
	>
	{
		private:friend class LinkedList;
		
		//-----------------[data]-----------------
		private:LinkedList* fromList;	//所属链表
		private:Node*		current;	//当前指针
		//-----------------[data]-----------------
		
		//构造函数 
		public:iterator(LinkedList& llist, Node* nowAt):
		fromList(&llist), current(nowAt){}
		
		//拷贝构造函数 
		public:iterator(const iterator& another):
		fromList(another.fromList), current(another.current){}
		
		//委托构造函数 
		public:iterator(LinkedList& llist):iterator(llist, llist.entry){}
		
		//默认构造函数：创建一个无效的迭代器
		public:iterator(void):fromList(nullptr), current(nullptr){}
		
		//返回迭代器是否有效 
		public:bool loaded(void) {
			return fromList != nullptr  &&  current != nullptr;
		}
		
		//返回所在链表
		public:LinkedList& lList(void)
		{
			if(fromList != nullptr) return *fromList;
			else throw "Iterator not belong to any list.";
		}
		
		//测试所在链表是否为空
		public:bool inEmpty(void)
		{
			return fromList->empty();
		}
		
		//测试迭代器是否处于首位置
		public:bool isBegin(void)
		{
			return current == fromList->entry->next;
		}
		
		//测试迭代器是否处于末端位置	
		public:bool isEnd(void)
		{
			return current == fromList->entry;
		}
		
		//后置自增重载：向后移动，遍历到最后一个元素后不会跳过nil结点
		public:iterator operator ++ (int)
		{
			iterator tmp(*this);
			current = current->next;
			return tmp;
		}
		
		//前置自增重载：向后移动，遍历到最后一个元素后不会跳过nil结点
		public:iterator& operator ++ (void)
		{
			current = current->next;
			return *this;
		}
		
		//后置自减重载：向前移动，遍历到第一个元素后不会跳过nil结点
		public:iterator operator -- (int)
		{
			iterator tmp(*this);
			current = current->pre;
			return tmp;
		}
		
		//前置自增重载：向前移动，遍历到第一个元素后不会跳过nil结点
		public:iterator& operator -- (void)
		{
			current = current->pre;
			return *this;
		}
		
		//解引用，若当前迭代器无效，抛出异常
		public:ElementType& operator * (void) const
		{
			if(current != nullptr && fromList != nullptr) return current->data;
			else throw "Iterator disabled";
		}
		
		//解引用，若当前迭代器无效，抛出异常
		public:ElementType* operator -> (void) const
		{
			return &(operator*());
		}
		
		//比较相等运算符重载
		public:bool operator == (const iterator& another) const
		{
			return current == another.current;
		}
		
		//比较不相等运算符重载
		public:bool operator != (const iterator& another) const
		{
			return current != another.current;
		}
		
		//赋值运算符已显式重载
		public:iterator& operator = (const iterator& another)
		{
			current = another.current;
			fromList = another.fromList;
			return *this;
		}
		
		//删除迭代器所指向的节点，并使得迭代器指向下一个节点 
		public:void erase(void)
		{
			fromList->erase(*this);
		}
		
		//向指定迭代器的前端插入一个新的元素节点，返回指向新元素节点的迭代器
		public:iterator insert_to_front(const ElementType& e)
		{
			return LinkedList::insert_to_front(*this, e);
		}
		
		//向指定迭代器的后端插入一个新的元素节点，返回指向新元素节点的迭代器
		public:iterator insert_to_back(const ElementType& e)
		{
			return LinkedList::insert_to_back(*this, e);
		}
		
		//将迭代器所指向的节点从原处摘下，插入到destination迭代器所指向的节点前
		//destination迭代器所指向的节点可以来自于其它链表实例 
		public:void pick_down_insert_front(iterator& destination)
		{
			LinkedList::pick_down_insert_front(*this, destination); 
		}
		
		//将迭代器所指向的节点从原处摘下，插入到destination迭代器所指向的节点后 
		//destination迭代器所指向的节点可以来自于其它链表实例 
		public:void pick_down_insert_back(iterator& destination)
		{
			LinkedList::pick_down_insert_back(*this, destination); 
		}
	};
	
	//部分数据成员，还有一部分在上面的迭代器类定义之前
	//-----------------[data]-----------------
	private:iterator start;			//起始迭代器
	private:const iterator finish;	//终止迭代器
	//-----------------[data]-----------------
	
	/*	设计细节：
	 *		用户开发者通过迭代器或成员函数访问元素
	 *		终止迭代器永远指向哨兵(nil)节点
	 *		当链表为空时，起始迭代器指向终止迭代器，并共同指向nil节点
	 *		当链表非空时，起始迭代器指向链表第一个元素
	 */
	 
	/*	特色功能：
	 *		设计了pick_down_insert_front和pick_down_insert_back方法
	 *		用于高效地将一个节点从原处“摘下”并安插到其它位置
	 */
	
	//创建一个空链表，初始化哨兵节点nil(在entry处)，初始化起始、终止迭代器指向nil
	public:LinkedList(void):
	entry(new Node()), start(*this), finish(start)
	{
		//空链表的头结点也是nil节点，pre和next指针都指向自己
		entry->next = entry->pre = entry;
	}
	
	//获取起始迭代器的副本 
	public:iterator begin(void)
	{
		return start;
	}
	
	//获取终止迭代器的副本 
	public:iterator end(void)
	{
		return finish;
	}
	
	//从链表前端删除一个数据节点 
	public:void pop_front(void)
	{
		if(!empty())
		{
			Node* firstNode = entry->next; //第一个节点 
			
			//更改链式结构 
			entry->next = firstNode->next;
			firstNode->next->pre = entry;
			
			//维护迭代器 
			++start;
			
			//释放内存 
			delete firstNode;
		}
		else throw "List is empty.";
	}
	
	//从链表后端删除一个数据节点 
	public:void pop_back(void)
	{
		if(!empty())
		{
			Node* lastNode = entry->pre; //最后一个节点 
			
			//更改链式结构 
			entry->pre = lastNode->pre;
			lastNode->pre->next = entry;
			
			//维护迭代器 
			start.current = entry->next;
			
			//释放内存 
			delete lastNode;
		}
		else throw "List is empty.";
	}
	
	//获取第一个节点的迭代器
	public:iterator first(void) {return begin();}
	//获取最后一个节点的迭代器
	public:iterator last(void)
	{
		iterator lastItr = end();
		return --lastItr;
	}
	
	//获取第一个节点的元素（可读可写） 
	public:ElementType& front(void)
	{
		return entry->next->data;
	}
	
	//获取最后的节点的元素（可读可写） 
	public:ElementType& back(void)
	{
		return entry->pre->data;
	}
	
	//获取最后一个节点的元素，并弹出。可连续使用 
	public:LinkedList& operator >> (ElementType& target)
	{
		target = back();
		pop_back();
		return *this;
	}
	
	//获取第一个节点的元素，并弹出。不可连续使用 
	public:friend ElementType& operator << (ElementType& target, LinkedList& l)
	{
		target = l.front();
		l.pop_front();
		return target;
	}
	
	//从前面插入一个新的元素节点，返回指向新元素节点的迭代器
	public:iterator push_front(const ElementType& e)
	{
		//创建新节点 
		Node* newNode = new Node(e);
		
		//更改链式结构 
		Node* oldNext = entry->next; 
		newNode->next = oldNext;
	  	newNode->pre  = entry;
		entry->next   = newNode;
		oldNext->pre  = newNode;
		
		//维护迭代器 
		start.current = newNode;
		
		return iterator(*this, newNode);
	}
	
	//从后面插入一个新的元素节点，返回指向新元素节点的迭代器
	public:iterator push_back(const ElementType& e)
	{
		//创建新节点 
		Node* newNode = new Node(e);
		
		//更改链式结构 
		Node* oldPre  = entry->pre;
		newNode->next = entry;
		newNode->pre  = oldPre;
		entry->pre    = newNode;
		oldPre->next  = newNode;
		
		//维护迭代器 
		start.current = entry->next;
		
		return iterator(*this, newNode);
	}
	
	//push_back的运算符重载，可连续使用 
	public:LinkedList& operator << (const ElementType& e)
	{
		push_back(e);
		return *this;
	}
	
	//push_front的运算符重载，不可连续使用 
	public:friend const ElementType& operator >> (const ElementType& e, LinkedList& l)
	{
		l.push_front(e);
		return e;
	}
	
	//向指定迭代器的前端插入一个新的元素节点，返回指向新元素节点的迭代器
	public:static iterator insert_to_front(iterator& itr, const ElementType& e)
	{
		//创建新节点 
		Node* newNode = new Node(e);
		
		//更改链式结构 
		Node* oldPre  = itr.current->pre;
		newNode->next = itr.current;
		newNode->pre  = oldPre;
		itr.current->pre = newNode;
		oldPre->next  = newNode;
		
		//维护迭代器 
		itr.fromList->start.current = itr.fromList->entry->next;
		
		return iterator(*itr.fromList, newNode);
	}
	
	//向指定迭代器的后端插入一个新的元素节点，返回指向新元素节点的迭代器
	public:static iterator insert_to_back(iterator& itr, const ElementType& e)
	{
		//创建新节点 
		Node* newNode = new Node(e);
		
		//更改链式结构 
		Node* oldNext = itr.current->next; 
		newNode->next = oldNext;
	  	newNode->pre  = itr.current;
		itr.current->next = newNode;
		oldNext->pre  = newNode;
		
		//维护迭代器 
		itr.fromList->start.current = itr.fromList->entry->next;
		
		return iterator(*itr.fromList, newNode);
	}
	
	//删除迭代器所指向的节点，并使得迭代器指向下一个节点 
	public:void erase(iterator& itr)
	{
		//检查迭代器是否属于本链表，且不允许擦除入口哨兵节点(nil) 
		if(itr.fromList != this || itr.current == entry) return;
		
		//更改链式结构
		Node* oldNxt = itr.current->next;
		itr.current->pre->next = oldNxt;
		itr.current->next->pre = itr.current->pre;
		
		//删除目标迭代器itr指向的节点 
		delete itr.current; 
		
		//使得目标迭代器itr指向下一个节点 
		itr.current = oldNxt;
		
		//维护迭代器
		start.current = entry->next;
	}
	
	//将source迭代器所指向的节点从原处摘下，插入到destination迭代器所指向的节点前
	//source迭代器所指向的节点可以来自于其它链表实例
	public:static void pick_down_insert_front(iterator& source, iterator& destination)
	{
		//避免"source"挂到"source"前面
		if(source == destination) return;
		
		//将source迭代器所指向的节点从原链表位置上摘下 
		source.current->pre->next = source.current->next;
		source.current->next->pre = source.current->pre;
		
		//将source迭代器所指向的节点插入到新的位置前 
		Node* oldPre  = destination.current->pre;
		source.current->next = destination.current;
		source.current->pre  = oldPre;
		destination.current->pre = source.current;
		oldPre->next  = source.current;
		
		//维护迭代器 
		destination.fromList->start.current = destination.fromList->entry->next;
		source.fromList->start.current = source.fromList->entry->next;
		
		//起始点迭代器所指向的节点允许为外来节点(另一个链表中的)，但需要更改其迭代器所属信息
		source.fromList = destination.fromList;
	}
	
	//将source迭代器所指向的节点从原处摘下，插入到destination迭代器所指向的节点后 
	//source迭代器所指向的节点可以来自于其它链表实例 
	public:static void pick_down_insert_back(iterator& source, iterator& destination)
	{
		//避免"source"挂到"source"后面
		if(source == destination) return;
		
		//将source迭代器所指向的节点从原链表位置上摘下 
		source.current->pre->next = source.current->next;
		source.current->next->pre = source.current->pre;
		
		//将source迭代器所指向的节点插入到新的位置后 
		Node* oldNext = destination.current->next; 
		source.current->next = oldNext;
	  	source.current->pre  = destination.current;
		destination.current->next = source.current;
		oldNext->pre  = source.current;
		
		//维护迭代器 
		destination.fromList->start.current = destination.fromList->entry->next;
		source.fromList->start.current = source.fromList->entry->next;
		
		//起始点迭代器所指向的节点允许为外来节点(另一个链表中的)，但需要更改其迭代器所属信息
		source.fromList = destination.fromList;
	}
	
	//将first到last迭代器所指向的区间部分截断，加入到指定位置前部
	//需要用户开发者保证destination不位于first到last之间
	public:static void pick_down_insert_front(iterator& first, iterator& last, iterator& destination)
	{
		//避免"first"挂到"first"前面
		if(first == destination) return;
		
		//将指定区间从原链表位置上摘下 
		first.current->pre->next = last.current->next;
		last.current->next->pre	 = first.current->pre;
		
		//将指定区间插入到新的位置前 
		Node* oldPre = destination.current->pre;
		last.current->next = destination.current;
		first.current->pre = oldPre;
		destination.current->pre = last.current;
		oldPre->next = first.current;
		
		//维护迭代器 
		destination.fromList->start.current = destination.fromList->entry->next;
		first.fromList->start.current = first.fromList->entry->next;
		
		//起始点迭代器所指向的节点允许为外来节点(另一个链表中的)，但需要更改其迭代器所属信息
		first.fromList = last.fromList = destination.fromList;
	}
	
	//将first到last迭代器所指向的区间部分截断，加入到指定位置后部
	//需要用户开发者保证destination不位于first到last之间
	public:static void pick_down_insert_back(iterator& first, iterator& last, iterator& destination)
	{
		//避免"first"挂到"first"前面
		if(first == destination) return;
		
		//将指定区间从原链表位置上摘下 
		first.current->pre->next = last.current->next;
		last.current->next->pre	 = first.current->pre;
		
		//将source迭代器所指向的节点插入到新的位置后 
		Node* oldNext = destination.current->next; 
		last.current->next = oldNext;
	  	first.current->pre = destination.current;
		destination.current->next = first.current;
		oldNext->pre  = last.current;
		
		//维护迭代器 
		destination.fromList->start.current = destination.fromList->entry->next;
		first.fromList->start.current = first.fromList->entry->next;
		
		//起始点迭代器所指向的节点允许为外来节点(另一个链表中的)，但需要更改其迭代器所属信息
		first.fromList = last.fromList = destination.fromList;
	}
	
	//判断链表是否为空
	public:bool empty(void)
	{
		return entry->next == entry;
	}
	
	//清空链表
	public:void clear(void)
	{
		Node* eachNode = entry->next;
		Node* eachNext = eachNode->next;
		
		//删除所有节点 
		while(eachNode != entry)
		{
			delete eachNode;
			
			eachNode = eachNext;
			eachNext = eachNode->next; 
		}
		
		//重新使入口节点的前后指针指向自己 
		entry->next = entry->pre = entry;
		
		//重置迭代器 
		start.current = entry;
	}
	
	//析构函数
	public:~LinkedList(void)
	{
		clear();
		delete entry;
	}
};
};
#endif
